This invention relates to a method and an apparatus for compiler processing, and also relates to a method of memory management which is usable in compiler processing.
In program translation processing, a source program written in a higher programming language is automatically translated into an object program in machine-language or assembler-language. Such program translation processing is generally called compiler processing. The compiler processing includes various types of sub processing, such as word and phrase analysis, syntax analysis, semantics analysis, optimization, and object code generation.
The word and phrase analysis has a process of reading the source program, and a process of resolving the source program into basic program elements such as constants, reserved words, and delimiters.
The syntax analysis procedure includes a process of checking whether or not statements composing the program are grammatically correct on the basis of the results of the word and phrase analysis, and a process of generating an intermediate code, hereinafter referenced as an intermediate language and various tables in accordance with the grammar. The intermediate language and the tables are used in the code generation. In the case of an interpreter, the syntax analysis is final processing.
The code generation procedure includes a process of generating the object program from information of memory area allocation and the intermediate language which results from the syntax analysis.
The optimization procedure includes a process of shortening The execution time of the generated object program, and a process of reducing the memory area occupied by the object program.
In general, the syntax analysis uses a tree structure, for example, a list structure, as an intermediate language in order to enable efficient optimization. This is because the list structure has the following advantage. In the list structure, nodes (such as list structure elements) can be dynamically changed in position so that processing such as moving codes can be easily done. Accordingly, using the list structure enables easy optimization of a program to be compiled.
However, in the case of the list structure is used, there occur the following problems. Since a system call is performed to an operating system (OS) to require a memory area at any time during the execution of optimization, the processing time is increased by a kernel call. Fragmentation is caused by the consumption and the release of a memory which occur during the execution of compiling.
To prevent such problems, it is desirable to use arrays of a static structure as much as possible. In the case where such arrays are used, a memory area for compiler processing is previously allocated. Since the compiler can freely use this memory area, a kernel call is unnecessary and a problem of fragmentation is prevented.
Most of the parallel processing languages used for multi-processor parallel computers have two parts for expressing calculation (arithmetic operation) and data transfer respectively. Even in the case of a parallel processing language which does not have an explicit data transfer part, a data transfer part results during the processing. A multi-processor parallel computer needs an exchange of data between processors, thereby requiring data transfer.
The total processing time P.sub.EXEC for a given task in parallel processing can be expressed by use of the total processing time S.sub.EXEC for the same task in sequential processing as indicated by the following equation. EQU P.sub.EXEC =P+S.sub.EXEC /N+T
where N denotes the degree of parallel, and T denotes the data transfer time and P denotes the start-up time of the parallel processing. As understood from the above-mentioned equation, the efficiency of the parallel processing can be increased by shortening the data transfer time T.
One conceivable way of shortening the data transfer time T is that the processing of a data transfer part is executed by DMA (direct memory access) transfer during an interval where a processor internally executes calculation and thus does not use a bus. This enables the processing of the calculation part and the processing of the data transfer part to be executed in parallel. In order to realize this approach, the optimization is required to execute an operation of moving codes of the data transfer part to positions prior to codes of the calculation part and an operation of generating a code for starting up the DMA transfer. Such movement of codes is difficult when an intermediate language is expressed by use of an array.
A data structure such as a list structure enables easy movement of codes as described previously, but its generation requires a kernel call which spends a relatively long processing time.